For the parallel machine scheduling problem of minimizing the maximum completion time, an Improved Discrete Artificial Bee Colony algorithm (IDABC) was proposed by considering the processing efficiency of the machine and the delivery time of the product as well as introducing the mathematical model of the problem. Firstly, a uniformly distributed population and a generation strategy of the parameters to be optimized were achieved by adopting the population initialization strategy, resulting in the improvement of the convergence speed of population. Secondly, the mutation operator in the differential evolution algorithm and the idea of simulated annealing algorithm were used to improve the local search strategy for the employed bee and the following bee, and the scout bee was improved by using the high-quality information of the optimal solution, resulting in the increasement of the population diversity and the avoidance of trapping into the local optimum. Finally, the proposed algorithm was applied in the parallel machine scheduling problem to analyze the performance and parameters of the algorithm. The experimental results on 15 examples show that compared with the Hybrid Discrete Artificial Bee Colony algorithm (HDABC), IDABC has the accuracy and stability improved by 4.1% and 26.9% respectively, and has better convergence, which indicates that IDABC can effectively solve the parallel machine scheduling problem in the actual scene.